package com.sort;

import utils.CreateArr;

/**
 * 3)
 * [归并排序] :小到大排序
 * 1.循环的将每一个部分都分为原来的一半,直到最后每一部分只剩下一个元素
 * 2.循环的将每两个部分进行合并并且排序,直到最后全部合并
 * O(n*log n)
 */
public class MergeSort {
    //对arr[l.....r]的部分进行排序

    static int[] mergeSort_1(int[] arr) {
        return __mergeSort(arr, 0, arr.length - 1);
    }

    /*优化3 :
     *  注意看第一步,将每个大的部分都切分为原来的一半,直到最后只剩下一个元素,但是从计算机本身的视角来看,他始终是同一个数组,
     *  因此循环的二分操作可以帮助我们理解原理,但是对计算机来说却无异于徒增负担.
     *  因此这里就没有必要执行切分操作,可以直接把它看做是已经切分成了多个小部分,直接归并就好.
     *  常用于链表排序
     */
    static int[] mergeSort(int[] arr) {
        for (int part = 1; part <= arr.length; part += part) {
            for (int i = 0; i + part < arr.length; i += 2 * part) {
                if ((i + 2 * part - 1 > arr.length - 1)) {
                    __merge(arr, i, i + part - 1, arr.length - 1);
                } else {
                    __merge(arr, i, i + part - 1, i + 2 * part - 1);
                }
            }
        }
        return arr;
    }


    private static int[] __mergeSort(int[] arr, int left, int right) {
//优化        if (left >= right) {
//优化            return arr;
//优化        }
        /*优化开始*/
        if (right - left <= 10) {
            int[] temparr = new int[right - left + 1];
            for (int i = left; i <= right; i++) {
                temparr[i - left] = arr[i];
            }
            //使用插入排序进行底层的排序,优化归并排序不断递归到底的消耗
            temparr = InsertionSort.insertionSort_3(temparr);
            for (int i = left; i <= right; i++) {
                //把 temparr 再回填回到 arr 中
                arr[i] = temparr[i - left];
            }
            return arr;
        }
        /*优化结束*/
        //得到中点位置的下标middle,注意这里最好不要使用 int middle = (right + left) / 2 ,防止 right + left 数据太大造成溢出
        int mid = (right - left) / 2 + left;
        //1.循环的将每一个部分都分为原来的一半,直到最后每一部分只剩下一个元素
        __mergeSort(arr, left, mid);
        __mergeSort(arr, mid + 1, right);
        //2.循环的将每两个部分进行合并并且排序,直到最后全部合并
        // if 条件判断当这两部分需要排序时(即前一部分的最大值要比后一部分的最小值大时),进行排序,否则直接合并即可
        if (arr[mid] > arr[mid + 1]) {
            __merge(arr, left, mid, right);
        }
        return arr;
    }

    //将 arr[left....mid] 与 arr[mid + 1....right] 两个部分进行归并
    private static int[] __merge(int[] arr, int left, int mid, int right) {
        int[] temarr = new int[right + 1 - left]; //开辟新的空间,这个空间是用来进行排序
        // 将 arr 中所有元素复制一份,到 temarr 中,注意这里 arr 是从下标 left 开始的,而 temarr 是从下标 0 开始的
        for (int i = left; i < right + 1; i++) {
            temarr[i - left] = arr[i];
        }
        int i = left;  //作为前一部分将要排序的元素的下标
        int j = mid + 1;    //作为后一部分将要排序的元素的下标
        for (int k = left; k <= right; k++) {  //k为arr数组中本轮归并中最小值将要覆盖掉的下标
            //防止越界,要保证i始终属于前一部分,j始终属于后一部分
            if (i > mid) {  //表明前一部分已经遍历结束,只需要把后一部分的值依次填入即可
                arr[k] = temarr[j - left];
                j++;
            } else if (j > right) {
                arr[k] = temarr[i - left]; //同理,后一部分已经遍历完毕,只需依次填入前一部分即可
                i++;
            }

            //一般情况 : 遍历整个数组,比较 temarr[i - left] 与 temarr[j - left] 的大小,将小的直接覆盖原数组arr,将它排到前面,并且将排完序的下标后移
            else if (temarr[i - left] < temarr[j - left]) {
                arr[k] = temarr[i - left];
                i++;
            } else {
                arr[k] = temarr[j - left];
                j++;
            }
        }
        return temarr;
    }

    public static void main(String[] args) {
        int[] arr = mergeSort(CreateArr.createRandomInt(21, 5, 1000));

        System.out.print("\n排序后 : ");
        for (int i : arr) {
            System.out.print(" " + i);
        }
    }
}